import java.util.*;

class Algorithm<T extends Comparable<T>>{
    public T maxVal(T[] arr){
        T max=arr[0];
        for(int i=1;i<arr.length;i++){
            if(max.compareTo(arr[i])<0){
                max=arr[i];
            }
        }
        return max;
    }
}

class Algorithm2{

    public static<T extends Comparable<T>> T maxVal(T[] arr){
        T max=arr[0];
        for(int i=1;i<arr.length;i++){
            if(max.compareTo(arr[i])<0){
                max=arr[i];
            }
        }
        return max;
    }





//    public static int maxVal(int[] arr){
//        int max=arr[0];
//        for(int i=1;i<arr.length;i++){
//            if(max<arr[i]){
//                max=arr[i];
//            }
//        }
//        return max;
//    }
}



class BinarySearchTree {

    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;


    public TreeNode search(int key) {
        if(root==null){
            return null;
        }
        while(root!=null){
            if(key<root.val){
                root=root.left;
            }else if(key>root.val){
                root=root.right;
            }else{
                return root;
            }
        }
        return null;
    }
    public void insertTree(int val) {
        if(root == null) {
            root = new TreeNode(val);
        }
        TreeNode cur=root;
        TreeNode prev=cur;
        while(cur!=null){
            if(cur.val<val){
                prev=cur;
                cur=cur.right;
            }else{
                prev=cur;
                cur=cur.left;
            }
        }
        if(prev.val<val){
            prev.right=new TreeNode(val);
        }else{
            prev.left=new TreeNode(val);
        }
    }
}
class MyArrayList<T>{
    public static void printAll(MyArrayList<? extends Number> list) {

    }
}
public class MyPriorityQueue {



    public static void main(String[] args) {



        Integer[] arr={7,10,90,67,88};
        Integer max=Algorithm2.maxVal(arr);
        System.out.println(max);





//        Algorithm<Integer> algorithm=new Algorithm<Integer>();
//        Integer[] arr={7,10,90,67,88};
//        int max=algorithm.maxVal(arr);
//        System.out.println(max);
    }



    public static void main2(String[] args) {






        int[] arr={27,15,19,18,28,34,65,49,25,37};//数组
//        InsertSort(arr);
//        HalveInsertSort(arr);
//        selectSort(arr);
//        TwoWaySelectSort(arr);
//        heapSort(arr);
//        bubbleSort(arr);
//        quickSort(arr);
//        quickSort(arr);
//        quickSort(arr);
//        int[] tmp=new int[arr.length];
//        mergeSort(arr,0,arr.length-1,tmp);
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void mergeSorts(int[] arr,int gap){
        int s1=0;
        int e1=s1+gap-1;
        int s2=e1+1;
        int e2=Math.min(arr.length-1,s2+gap-1);
        int[] tmp=new int[arr.length];
        int k=0;
        while(s2<arr.length){
            while(s1<=e1&&s2<=e2){
                if(arr[s1]<=arr[s2]){
                    tmp[k++]=arr[s1++];
                }else{
                    tmp[k++]=arr[s2++];
                }
            }
            while(s1<=e1){
                tmp[k++]=arr[s1++];
            }
            while(s2<=e2){
                tmp[k++]=arr[s2++];
            }
            s1=e2+1;
            e1=s1+gap-1;
            s2=e1+1;
            e2=Math.min(arr.length-1,s2+gap-1);
        }
        while(s1<=arr.length-1){
            tmp[k++]=arr[s1++];
        }
        for(int i=0;i<k;i++){
            arr[i]=tmp[i];
        }
    }
    public static void mergeSort(int[] arr){
        for(int gap=1;gap<arr.length;gap*=2){
            mergeSorts(arr,gap);
        }
    }






//    public static void merge(int[] arr,int low,int mid,int high,int[] tmp){
//        int i = 0;
//        int j = low,k = mid+1;
//        while(j <= mid && k <= high){
//            if(arr[j] < arr[k]){
//                tmp[i++] = arr[j++];
//            }else{
//                tmp[i++] = arr[k++];
//            }
//        }
//        while(j <= mid){
//            tmp[i++] = arr[j++];
//        }
//
//        while(k <= high){
//            tmp[i++] = arr[k++];
//        }
//
//        for(int t=0;t<i;t++){
//            arr[low+t] = tmp[t];
//        }
//    }
//
//    public static void mergeSort(int[] arr,int low,int high,int[] tmp){
//        if(low<high){
//            int mid = (low+high)/2;
//            mergeSort(arr,low,mid,tmp);
//            mergeSort(arr,mid+1,high,tmp);
//            merge(arr,low,mid,high,tmp);
//        }
//    }






    public static int partition(int[] arr,int start,int end){
        int tmp=arr[start];
        while(start<end){
            while(start<end&&arr[end]>=tmp){
                end--;
            }
            arr[start]=arr[end];
            while(start<end&&arr[start]<=tmp){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[start]=tmp;
        return start;
    }
    public static void quickSort(int[] arr){
        int left=0;
        int right=arr.length-1;
        Stack<Integer> stack=new Stack<>();
        int pivot=partition(arr,left,right);
        if(left+1<pivot){
            stack.add(left);
            stack.add(pivot-1);
        }
        if(right-1>pivot){
            stack.add(pivot+1);
            stack.add(right);
        }
        while(!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            pivot=partition(arr,left,right);
            if(left+1<pivot){
                stack.add(left);
                stack.add(pivot-1);
            }
            if(right-1>pivot){
                stack.add(pivot+1);
                stack.add(right);
            }
        }
    }




//    public static int partition(int[] arr,int start,int end){
//        int i=start;
//        int j=end;
//        int tmp=arr[i];
//        while(i<j){
//            while(i<j&&arr[j]>=tmp){
//                j--;
//            }
//            while(i<j&&arr[i]<=tmp){
//                i++;
//            }
//            swap(arr,i,j);
//        }
//        swap(arr, start,i);
//        return i;
//    }
//    public static void quickSorts(int[] arr,int left,int right){
//        if(left>=right){
//            return;
//        }
//        int pivot=partition(arr,left,right);
//        quickSorts(arr,left,pivot-1);
//        quickSorts(arr,pivot+1,right);
//    }
//    public static void quickSort(int[] arr){
//        quickSorts(arr,0,arr.length-1);
//    }







//    public static int partition(int[] arr,int start,int end){
//        int tmp=arr[start];
//        while(start<end){
//            while(start<end&&arr[end]>=tmp){
//                end--;
//            }
//            arr[start]=arr[end];
//            while(start<end&&arr[start]<=tmp){
//                start++;
//            }
//            arr[end]=arr[start];
//        }
//        arr[start]=tmp;
//        return start;
//    }
//    public static void quickSorts(int[] arr,int left,int right){
//        if(left>=right){
//            return;
//        }
//        int pivot=partition(arr,left,right);
//        quickSorts(arr,left,pivot-1);
//        quickSorts(arr,pivot+1,right);
//    }
//    public static void quickSort(int[] arr){
//        quickSorts(arr,0,arr.length-1);
//    }






    public static void bubbleSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            boolean bool=true;
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j+1]<arr[j]){
                    swap(arr,j+1,j);
                    bool=false;
                }
            }
            if(bool){
                break;
            }
        }
    }





    public static void shiftDown(int[] arr,int parent,int len){
        int child=parent*2+1;
        while(child<len){
            if(child+1<len&&arr[child]<arr[child+1]){
                child++;
            }
            if(arr[child]>arr[parent]){
                swap(arr,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }
    public static void MySort(int[] arr){
        for(int i=(arr.length-1)/2;i>=0;i--){
            shiftDown(arr,i,arr.length);
        }
    }
    public static void heapSort(int[] arr){
        MySort(arr);
        int end=arr.length-1;
        while(end>0){
            swap(arr,0,end);
            shiftDown(arr,0,end);
            end--;
        }
    }







    public static void TwoWaySelectSort(int[] arr){
        int left=0;
        int right=arr.length-1;
        while(left<=right){
            int min=left;
            int max=left;
            for(int i=left+1;i<=right;i++){
                if(arr[i]>arr[max]){
                    max=i;
                }
                if(arr[i]<arr[min]){
                    min=i;
                }
            }
            swap(arr,min,left);
            if(max==left){
                max=min;
            }
            swap(arr,max,right);
            left++;
            right--;
        }
    }







    public static void selectSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            int max=0;
            for(int j=1;j<arr.length-i;j++){
                if(arr[j]>arr[max]){
                    max=j;
                }
            }
            int tmp=arr[max];
            arr[max]=arr[arr.length-1-i];
            arr[arr.length-1-i]=tmp;
        }
    }






    public static void shellSort(int[] arr){
        int gap=arr.length;
        while(gap>0){
            mySort(arr,gap);
            gap/=2;
        }
    }
    public static void mySort(int[] arr,int gap){
        for(int i=gap;i<=arr.length;i++){
            int tmp=arr[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(arr[j]>tmp){
                    arr[j+gap]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }








    public static void HalveInsertSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int left=0;
            int right=i-1;
            int tmp=arr[i];
            while(right>=left){
                int mid=(left+right)/2;
                if(arr[mid]>tmp){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }
            for(int j=i-1;j>right;j--){
                arr[j+1]=arr[j];
            }
            arr[right+1]=tmp;
        }
    }




    public static void InsertSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int tmp=arr[i];
            int j=i-1;
            for(;j>=0;j--){
                if(arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }














    public static void main1(String[] args) {
        PriorityQueue queue1=new PriorityQueue();
        PriorityQueue<Integer> queue2=new PriorityQueue<>();
        PriorityQueue<Integer> queue3=new PriorityQueue<>(10);
        PriorityQueue<Integer> queue4=new PriorityQueue<>(10, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        PriorityQueue<Integer> queue5=new PriorityQueue<>(queue1);
        PriorityQueue<Integer> queue6=new PriorityQueue<>(new SortedSet<Integer>() {
            @Override
            public Comparator<? super Integer> comparator() {
                return null;
            }

            @Override
            public SortedSet<Integer> subSet(Integer fromElement, Integer toElement) {
                return null;
            }

            @Override
            public SortedSet<Integer> headSet(Integer toElement) {
                return null;
            }

            @Override
            public SortedSet<Integer> tailSet(Integer fromElement) {
                return null;
            }

            @Override
            public Integer first() {
                return null;
            }

            @Override
            public Integer last() {
                return null;
            }

            @Override
            public int size() {
                return 0;
            }

            @Override
            public boolean isEmpty() {
                return false;
            }

            @Override
            public boolean contains(Object o) {
                return false;
            }

            @Override
            public Iterator<Integer> iterator() {
                return null;
            }

            @Override
            public Object[] toArray() {
                return new Object[0];
            }

            @Override
            public <T> T[] toArray(T[] a) {
                return null;
            }

            @Override
            public boolean add(Integer integer) {
                return false;
            }

            @Override
            public boolean remove(Object o) {
                return false;
            }

            @Override
            public boolean containsAll(Collection<?> c) {
                return false;
            }

            @Override
            public boolean addAll(Collection<? extends Integer> c) {
                return false;
            }

            @Override
            public boolean retainAll(Collection<?> c) {
                return false;
            }

            @Override
            public boolean removeAll(Collection<?> c) {
                return false;
            }

            @Override
            public void clear() {

            }
        });
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        queue.add(1);
        queue.offer(2);
        queue.remove(1);
        queue.element();
        int i=queue.peek();
        queue.clear();
        queue.comparator();
        queue.contains(10);
        queue.iterator();
        Object[] ret=queue.toArray();
        int size=queue.size();
        int[] arr={27,15,19,18,28,34,65,49,25,37};//数组

        shiftUp(arr,arr.length-1);//调用函数
        System.out.println(Arrays.toString(arr));//输出
    }
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] ret=new int[k];//返回的数组
        if(k==0){//如果k==0直接返回
            return ret;
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override//创建队列，通过Comparator调整为大堆
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int i=0;
        while(i<arr.length){//遍历数组
            if(i<k){//大堆没满时，直接放入
                queue.add(arr[i]);
            }else{
                if(arr[i]<=queue.peek()){//当前数据小于等于大堆顶元素。
                    queue.poll();//删除堆顶元素
                    queue.add(arr[i]);//放入当前元素
                }
            }
            i++;
        }
        for(int j=0;j<k;j++){
            ret[j]=queue.poll();//把大堆元素全部放到数组中。
        }
        return ret;
    }






    public static void shiftUp(int[] arr,int index){
        while(index>0){
            int parent=(index-1)/2;
            if(arr[parent]<=arr[index]){
                break;
            }
            int tmp=arr[parent];
            arr[parent]=arr[index];
            arr[index]=tmp;
            index=parent;
        }
    }





    public static void heapSort1(int[] arr){
        mySort1(arr);//先将整个数组调整为大根堆
        int end=arr.length-1;//尾下标
        while(end>0){//循环将每个数据都与头交换
            swap(arr,0,end);//头尾交换
            shiftDown1(arr,0,end);//交换后让整个堆再次成为大根堆
            end--;//尾部向前移动，因为后面的已经有序了，我们就把需要调整的边界缩小。
        }
    }
    public static void mySort1(int[] arr){
        for(int i=(arr.length-1)/2;i>=0;i--){//最后的一颗子树根的位置就是i。
            shiftDown1(arr,i,arr.length);//把每一颗子树调整为大根堆
        }
    }
    public static void shiftDown1(int[] arr,int parent,int len){
        int child=parent*2+1;//得到每一颗子树的左节点
        while(child<len){//向下调整
            if(child+1<len&&arr[child]<arr[child+1]){//比较左右子树，找出最大的
                child++;
            }
            if(arr[child]>arr[parent]){//判断左右子树是否有大于当前节点
                swap(arr,child,parent);//交换
                parent=child;//继续向下调整
                child=parent*2+1;//得到要向下调整树的根节点
            }else{
                break;//如果左右孩子都不大于当前根节点，证明此时当前子树已经为最大堆。
            }
        }
    }
    public static void swap(int[] arr,int x,int y){//交换函数
        int tmp=arr[x];
        arr[x]=arr[y];
        arr[y]=tmp;
    }
}
